In all different types of MAP-based (Maximum A Posteriori probability) algorithms, the decoding of the MAP parameters, i.e., a.sub.k and B.sub.k parameters, that represent probabilities of the states of the trellis at time k conditioned on the past received signals and the probabilities of the trellis states at time k conditioned on the future received signals, respectively, is determined in a forward and backward recursion. As shown in FIG. 1, after computation (102) of .gamma..sub.j (R.sub.k,s',s), alpha and beta parameters for all N data bits are computed (104, 108) and stored (106, 110) in memory, where N is a preselected integer. Then the conditional joint probability .GAMMA..sub.i is computed (112) based on the N values for alpha and the N values for beta. This approach requires storing all the information related to alpha and beta information for the entire data block. The MAP decoding algorithm is described in more detail below.
The MAP decoding algorithm is a recursive technique that computes the Log-Likelihood Ratio (LLR) as: ##EQU1##
where R.sub.k ={d.sub.k.sup.r, y.sub.k.sup..eta. } and s' and s are the previous and current states of the system. d.sub.k.sup.r and y.sub.k.sup..eta. are the received data and parity bit from the i-th encoder. .alpha..sub.k (s) and .beta..sub.k (s) are computed recursively as: ##EQU2##
where h.sub..alpha. and h.sub..beta. are normalization factors. .gamma..sub.j (R.sub.k,s',s) is computed from transition probabilities of the channel, and here the channel is assumed to be a discrete Gaussian memoryless channel. .gamma..sub.j (R.sub.k,s',s) is described as: EQU .gamma..sub.j (R.sub.k,s',s)=Pr{R.sub.k.vertline.d.sub.k =j, S.sub.k =s, S.sub.k-1 =s'}.times.Pr{d.sub.k =j.vertline.S.sub.k =s, S.sub.k-1 =s'}.times.Pr{S.sub.k =s .vertline.S.sub.k-1 =s'} (4)
The second term in (4) is the transition probability of the discrete channel; the third term is equal to 1 or 0 depending on whether it is possible to go from state s' to state s when the input data is j; and the fourth term is the transition state probabilities and, for equiprobable binary data, it is equal to 1/2. Considering R.sub.k ={u.sup.r.sub.k, y.sup.ri.sub.k }, u.sup.r.sub.k and y.sup.ri.sub.k are two uncorrelated Gaussian variables conditioned on (d.sub.k =j, S.sub.k =s, S.sub.k-1 =s'}, therefore, the second term in (4) may be divided into two terms: EQU Pr{R.sub.k.vertline.. . . }=Pr{u.sup.r.sub.k.vertline.. . . }.times.Pr{y.sup.ri.sub.k.vertline.. . . }
If the Turbo block length is equal to N, all N data and parity bits must be received before the beta parameters are computed. Then, the backward recursion may be used to compute beta parameters using equation (3) above. Since the final soft output decoded data are computed using equation (1), all alpha and beta parameters for the entire data sequence are retained to finish the computations. If the memory length of recursive systematic convolutional (RSC) codes in Turbo code is equal to m, then a total of 2.sup.m states exist for each decoder. Therefore, a total of 2.sup.m.multidot. N memory space is required for keeping the alpha or beta parameters. Also, the decoded data will be available at the end after finishing computation of alpha and beta parameters and using equation (1).
Thus, there is a need for a method, computer medium and device that minimize memory is requirements for computing MAP-based decoding algorithms.